    /*
     * 最小编辑距离
     *
     * */
    public class Solution {
        public int min(int a1, int a2, int a3) {
            int min = a1 < a2 ? a1 : a2;
            min = min < a3 ? min : a3;
            return min;
        }

        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] minDis = new int[len1 + 1][len2 + 1];
            for (int i = 0; i <= len2; i++) {
                minDis[0][i] = i;
            }
            for (int i = 1; i <= len1; i++) {
                minDis[i][0] = i;
            }
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    //删除
                    int path1 = minDis[i - 1][j] + 1;
                    //插入
                    int path2 = minDis[i][j - 1] + 1;
                    //替换
                    int path3 = minDis[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1);
                    minDis[i][j] = min(path1, path2, path3);
                }
            }
            return minDis[len1][len2];
        }
    }